import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class PreorderTraversal {
    // 二叉树的前序遍历
    // https://www.nowcoder.com/practice/5e2135f4d2b14eb8a5b06fab4c938635?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    private List<Integer> ret;
    public int[] preorderTraversal1 (TreeNode root) {
        // write code here
        ret = new ArrayList<>();
        preorderTraversalChild(root);
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    private void preorderTraversalChild(TreeNode root) {
        if (root == null) {
            return;
        }
        ret.add(root.val);
        preorderTraversalChild(root.left);
        preorderTraversalChild(root.right);
    }

    // 非递归
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        List<Integer> ret = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                ret.add(cur.val);
                stack.addLast(cur);
                cur = cur.left;
            }
            if (!stack.isEmpty()) {
                cur = stack.pollLast().right;
            }
        }
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        PreorderTraversal preorderTraversal = new PreorderTraversal();
        TreeNode root = new TreeNode(2);
        root.right = new TreeNode(4);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(1);
        root.right.left.right = new TreeNode(3);
        System.out.println(preorderTraversal.preorderTraversal(root));
    }
}
